package com.leetcode.algorithm.y22.m08.w3;

import java.util.Arrays;

/**
 * 435. 无重叠区间
 * 
 * https://leetcode.cn/problems/non-overlapping-intervals/
 * 
 * @author jie.deng
 *
 */
class Question0435Solution02 {

	public int eraseOverlapIntervals(int[][] intervals) {
		// 将题目转化为求非交叉区间的最大个数
		// 按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
		// 局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。
		// 全局最优：选取最多的非交叉区间。
		int len = intervals.length;

		// 按照右边界排序
		Arrays.sort(intervals, (arr1, arr2) -> (arr1[1] - arr2[1]));

		int max = 1;
		int right = intervals[0][1];
		for (int i = 1; i < len; i++) {
			if (intervals[i][0] >= right) {
				max++;
				right = intervals[i][1];
			}
		}

		return len - max;
	}

}